1. Field of the Invention
The present invention is related to decoders in communication systems and storage systems. More specifically, the present invention relates to decoders and decoding methods for low-density parity check codes constructed based on Reed-Solomon codes.
2. Description of the Prior Art
Research into low-density parity-check (LDPC) codes has attracted a tremendous amount of interest as a result of their near-capacity performance and their potential for highly-parallel decoder implementation. LDPC codes for several applications such as optical communications, and image transmission over wireless channels have previously been discussed. Many recent communication standards, such as IEEE 802.3an and 802.16e (WiMAX) have included LDPC codes. The LDPC code adopted in IEEE 802.3an is a regular code which is constructed based on a Reed-Solomon (RS) code with two information symbols. Construction methods of LDPC codes based shortened RS codes and extended RS codes were presented in “A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols” reported by I. Djurdjevic on IEEE Commun. Lett., vol. 7, no. 7, pp. 317-319, July 2003 and “Design of LDPC codes: A survey and new results” reported by G. Liva on J. Commun. Softw. Syst., vol. 2, no. 3, pp. 191-211, September 2006. The minimum Hamming distance of an RS-LDPC code is guaranteed and RS-LDPC codes with large minimum distances can be constructed. The (2048, 1723) RS-LDPC code adopted in IEEE 802.3an standard has an error floor of 10−13 which can meet the requirement of the standard. High-rate codes such as the (2048, 1723) code are often used for applications with relatively low-noise channels, where as many message bits as possible are required to be transmitted within a finite bandwidth. High-rate codes are usually used in wire-line communications such as the 802.3an and the storage systems such as the hard-disk drives. For these applications, high data throughput (>1 Gbit/s) is usually required.
An LDPC code can be decoded by performing message-passing decoding (MPD) through its Tanner graph, which is a bipartite graph consisting of variable nodes and check nodes. In “Low-density parity-check Codes” reported by R. Gallager on IRE Trans. Inf. Theory, vol. 7, pp. 21-28, January 1962 and “Good error correcting codes based on very sparse matrices” reported by D. J. C. Mackay on IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399-431, March 1999, a decoding schedule called two-phase message passing (TPMP), which divides the decoding operations in one iteration into check-node-operation and variable-node-operation phases, is used. Layered MPD and shuffled MPD can be used to increase the convergence speed in bit-error-rate (BER) performance and, hence, reduce the number of iterations required to achieve a given BER performance.
To implement a high-throughput decoder, a fully-parallel architecture can be adopted, but with complex inter-connections. In order to reduce the routing complexity, a bit-serial architecture or a stochastic decoder can be used. The technique of wire partitioning can be used to shorten the critical-path delay and further increase the throughput. The decoders presented in “A 690-mW 1-Gb/s 1024-b, rate-½ low-density parity-check code decoder” reported by A. J. Blanksby on IEEE J. Solid-State Circuits, vol. 37, no. 3, pp. 404-412, March 2002, “A scalable LDPC decoder ASIC architecture with bit-serial message exchange” reported by T. Brandon on Integration, vol. 41, no. 3, pp. 385-398, May 2008, “Fully parallel stochastic LDPC decoders” reported by S. S. Tehrani on IEEE Trans. Signal Processing, vol. 56, no. 11, pp. 5692-5703, November 2008, and “Design of high-throughput fully parallel LDPC decoders based on wire partitioning” reported by N. Onizawa, on IEEE Trans. Very Large Scale Integr. (VLSI) Syst. are single-mode rate-½ LDPC decoders, where the check-node degrees are low, e.g., 6. Fully-parallel decoders for a high-rate 2048-bit (6, 32)-regular LDPC code, where the variable-node and check-node degrees are 6 and 32, respectively, were presented in “Power reduction techniques for LDPC decoders” reported by A. Darabiha on IEEE J. Solid-State Circuits, vol. 43, no. 8, pp. 1835-1845, August 2008, “Block-interlaced LDPC decoders with reduced interconnect complexity” reported by A. Darabiha on IEEE Trans. Circuits. Syst. II, Exp. Briefs, vol. 55, pp. 74-78, January 2008, and “Multi-split-row threshold decoding implementations for LDPC codes” reported by T. Mohsenin, in Proc. IEEE ISCAS 2009, pp. 2449-2452, May 2009. In “Sliced message passing: high throughput overlapped decoding of high-rate low-density parity-check codes” reported by L. Liu on IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 55, no. 11, pp. 3697-3710, December 2008, the authors showed that the high check-node degree leads to greater complexities in hardware, interconnect, and timing, which are difficult to manage using a fully-parallel architecture. Consequently, they proposed sliced message passing (SMP), which is a register-based partially-parallel architecture, to design a high-throughput decoder for the (6, 32)-regular LDPC code. The complexity of the silicon-area for a fully-parallel LDPC decoder grows quickly as the code length increases. Consequently, long LDPC decoders with high check-node degrees were designed using partially-parallel architectures. However, most of these high-throughput decoders are based on TPMP, which cannot increase the convergence speed in BER performance.
A memory-shared partially-parallel architecture is more suitable for a multi-mode decoder, since most hardware resources can be shared among different modes. A partially-parallel architecture can be combined with layered MPD so as to increase the convergence speed. Many multi-mode decoders for WiMAX LDPC codes are implemented using memory-shared architectures based on a layered MPD. To implement a multi-mode decoder for quasi-cyclic (QC) LDPC codes, such as those specified in WiMAX, the permutators must be efficiently shared among different modes in order to reduce the implementation complexity. In “Configurable, high throughput, irregular LDPC decoder architecture tradeoff analysis and implementation” reported by M. Karkooti in Proc. IEEE 2006 Application-specific Systems, Architectures and Processors, pp. 360-367, September 2006, the authors proposed a multi-mode decoder architecture using flexible barrel shifters. In “Reconfigurable shuffle network design in LDPC decoder” reported by J. Tang, in Proc. IEEE 2006 Application-specific Systems, Architectures and Processors, pp. 81-86, September 2006, “Area efficient controller design of barrel shifters for reconfigurable LDPC decoders” reported by D. Oh in Proc. IEEE ISCAS 2008, pp. 240-243, May 2008, “Multi-mode message passing switch networks applied for QC-LDPC decode” reported by C. H. Liu in Proc IEEE ISCAS 2008, pp. 752-755, May 2008, and “Efficient shuffle network architecture and application for WiMAX LDPC decoders” reported by J. Lin, on IEEE Trans. Circuits. Syst. II, Exp. Briefs, vol. 54, no. 3, pp. 215-219, March 2009, several efficient and flexible permutator designs for multi-length multi-rate QC-LDPC decoders were presented. However, an efficient implementation of a high-throughput multi-mode LDPC decoder is a challenging task for memory-shared partially-parallel architectures.
The work related to RS-LDPC codes presented in “Power reduction techniques for LDPC decoders” by A. Darabiha on IEEE J. Solid-State Circuits, vol. 43, no. 8, pp. 1835-1845, August 2008 is single-mode. For a single-mode RS-LDPC decoder using a partially-parallel architecture, the shift-structured properties discovered in “Decoder design for RS-based LDPC codes” by J. Sha in IEEE Trans. Circuits. Syst. II, Exp. Briefs, vol. 56, no. 9, pp. 724-728, September 2009 and the MUX-based design adopted in “A 47 Gb/s LDPC decoder with improved low error rate performance” by Z. Zhang in 2009 IEEE VLSI Circuits Symposium, Kyoto, Japan, June 2009 can reduce the permutation complexity remarkability. However, for a multi-mode RS-LDPC decoder architecture, we require an efficient design of configurable permutators, which is one of the most challenging aspects, since the RS-LDPC codes are not QC codes.